Subshift of finite type

 ( Ergodic Theory ) 

In mathematics, subshifts of finite type are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics and ergodic theory. They also describe the set of all possible sequences executed by a finite-state machine. The most widely studied are the subshifts of finite type.

---

Motivating examples A (one-sided) shift of finite type is the set of all sequences, infinite on one end only, that can be made up of the letters $A,\; B,\; C$, like $AAA\backslash cdots,\; ABAB\backslash cdots,\; \backslash dots$. A (two-sided) shift of finite type is similar, but consists of sequences that are infinite on both ends.

A subshift can be defined by a directed graph on these letters, such as the graph $A\; \backslash to\; B\; \backslash to\; C\; \backslash to\; A$. It consists of sequences whose transitions between consecutive letters are only those allowed by the graph. For this example, the subshift consists of only three one-sided sequences: $ABCABC\backslash cdots,\; BCABCA\backslash cdots,\; CABCAB\backslash cdots$. Similarly, the two-sided subshift described by this graph consists of only three two-sided sequences.

Other directed graphs on the same letters produce other subshifts. For example, adding another arrow $A\backslash to\; C$ to the graph produces a subshift that, instead of containing three sequences, contains an uncountably infinite number of sequences.

---

Markov and non-Markov measures Given a Markov transition matrix and an invariant distribution on the states, we can impose a probability measure on the set of subshifts. For example, consider the Markov chain given on the left on the states $A,\; B\_1,\; B\_2$, with invariant distribution $\backslash pi\; =\; (2/7,\; 4/7,\; 1/7)$. If we "forget" the distinction between $B\_1,\; B\_2$, we project this space of subshifts on $A,\; B\_1,\; B\_2$ into another space of subshifts on $A,\; B$, and this projection also projects the probability measure down to a probability measure on the subshifts on $A,\; B$.

The curious thing is that the probability measure on the subshifts on $A,\; B$ is not created by a Markov chain on $A,\; B$, not even multiple orders. Intuitively, this is because if one observes a long sequence of $B^n$, then one would become increasingly sure that the $Pr(A\; |\; B^n)\; \backslash to\; \backslash frac\; 23$, meaning that the observable part of the system can be affected by something infinitely in the past.

Conversely, there exists a space of subshifts on 6 symbols, projected to subshifts on 2 symbols, such that any Markov measure on the smaller subshift has a preimage measure that is not Markov of any order (Example 2.6 ).

---

Definition Let be a finite set of symbols (alphabet). Let denote the set of all bi-infinite sequences of elements of together with the shift operator . We endow with the discrete topology and with the product topology. A symbolic flow or subshift is a closed set -invariant subset of Xie (1996) p.21 and the associated language is the set of finite subsequences of .Xie (1996) p.22

Now let be an adjacency matrix with entries in Using these elements we construct a directed graph with the set of vertices and the set of edges containing the directed edge in if and only if . Let be the set of all infinite admissible sequences of edges, where by admissible it is meant that the sequence is a walk of the graph, and the sequence can be either one-sided or two-sided infinite. Let be the left shift operator on such sequences; it plays the role of the time-evolution operator of the dynamical system. A subshift of finite type is then defined as a pair obtained in this way. If the sequence extends to infinity in only one direction, it is called a one-sided subshift of finite type, and if it is bilateral, it is called a two-sided subshift of finite type.

Formally, one may define the sequences of edges as

$\backslash Sigma\_\{A\}^\{+\}\; =\; \backslash left\backslash \{\; (x\_0,x\_1,\backslash ldots):$

x_j \in V, A_{x_{j}x_{j+1}}=1, j \in \N \right\}.

This is the space of all sequences of symbols such that the symbol can be followed by the symbol only if the -th entry of the matrix is 1. The space of all bi-infinite sequences is defined analogously:

$\backslash Sigma\_\{A\}\; =\; \backslash left\backslash \{\; (\backslash ldots,\; x\_\{-1\},x\_0,x\_1,\backslash ldots):$

x_j \in V, A_{x_{j}x_{j+1}}=1, j\in\mathbb{Z} \right\}.

The shift operator maps a sequence in the one- or two-sided shift to another by shifting all symbols to the left, i.e.

$\backslash displaystyle(T(x))\_\{j\}=x\_\{j+1\}.$

Clearly this map is only invertible in the case of the two-sided shift.

A subshift of finite type is called transitive if is strongly connected: there is a sequence of edges from any one vertex to any other vertex. It is precisely transitive subshifts of finite type which correspond to dynamical systems with orbits that are dense.

An important special case is the full -shift: it has a graph with an edge that connects every vertex to every other vertex; that is, all of the entries of the adjacency matrix are 1. The full -shift corresponds to the Bernoulli scheme without the measure.

---

Terminology By convention, the term shift is understood to refer to the full -shift. A subshift is then any subspace of the full shift that is shift-invariant (that is, a subspace that is invariant under the action of the shift operator), non-empty, and closed for the product topology defined below. Some subshifts can be characterized by a transition matrix, as above; such subshifts are then called subshifts of finite type. Often, subshifts of finite type are called simply shifts of finite type. Subshifts of finite type are also sometimes called topological Markov shifts.

---

Examples Many chaotic are isomorphic to subshifts of finite type; examples include systems with transverse homoclinic connections, of with a positive metric entropy, the Prouhet–Thue–Morse system, the Chacon system (this is the first system shown to be weakly mixing but not strongly mixing), and Toeplitz systems. Matthew Nicol and Karl Petersen, (2009) " Ergodic Theory: Basic Examples and Constructions", Encyclopedia of Complexity and Systems Science, Springer https://doi.org/10.1007/978-0-387-30440-3_177

---

Generalizations A sofic system is an image of a subshift of finite type where different edges of the transition graph may be mapped to the same symbol. For example, if one only watches the output from a hidden Markov chain, then the output appears to be a sofic system.'' target="_blank" rel="nofollow"> Sofic Measures: Characterizations of Hidden Markov Chains by Linear Algebra, Formal Languages, and Symbolic Dynamics'' - Karl Petersen, Mathematics 210, Spring 2006, University of North Carolina at Chapel Hill It may be regarded as the set of labellings of paths through an Automata theory: a subshift of finite type then corresponds to an automaton which is deterministic.Pytheas Fogg (2002) p.205 Such systems correspond to .

Context-free systems are defined analogously, and are generated by phrase structure grammars.

A renewal system is defined to be the set of all infinite concatenations of some fixed finite collection of finite words.

Subshifts of finite type are identical to free (non-interacting) one-dimensional (-letter generalizations of ), with certain nearest-neighbor configurations excluded. Interacting Ising models are defined as subshifts together with a continuous function of the configuration space (continuous with respect to the product topology, defined below); the partition function and Hamiltonian are explicitly expressible in terms of this function.

Subshifts may be quantized in a certain way, leading to the idea of the quantum finite automata.

---

Topology A subshift has a natural topology, derived from the product topology on where

$V^\backslash Z=\; \backslash prod\_\{n\; \backslash in\; \backslash Z\}\; V\; =\; \backslash \{\; x=(\backslash ldots,x\_\{-1\},x\_0,x\_1,\backslash ldots)\; :$

x_k \in V \; \forall k \in \Z \}

and is given the discrete topology. A basis for the topology of which induces the topology of the subshift, is the family of

$C\_ta\_0,=\; \backslash \{x\; \backslash in\; V^\backslash Z\; :$

x_t = a_0, \ldots ,x_{t+s} = a_s \}

The cylinder sets are in Every open set in is a countable union of cylinder sets. Every open set in the subshift is the intersection of an open set of with the subshift. With respect to this topology, the shift is a homeomorphism; that is, with respect to this topology, it is continuous with continuous inverse.

The space is homeomorphic to a Cantor set.

---

Metric A variety of different metrics can be defined on a shift space. One can define a metric on a shift space by considering two points to be "close" if they have many initial symbols in common; this is the p-adic metric. In fact, both the one- and two-sided shift spaces are compact space .

---

Measure A subshift of finite type may be endowed with any one of several different measures, thus leading to a measure-preserving dynamical system. A common object of study is the Markov measure, which is an extension of a Markov chain to the topology of the shift.

A Markov chain is a pair consisting of the transition matrix, an matrix for which all and

$\backslash sum\_\{j=1\}^np\_\{ij\}=1$

for all . The stationary probability vector has all , $\backslash sum\; \backslash pi\_i\; =\; 1$ and has

$\backslash sum\_\{i=1\}^n\; \backslash pi\_i\; p\_\{ij\}=\; \backslash pi\_j.$

A Markov chain, as defined above, is said to be compatible with the shift of finite type if whenever . The Markov measure of a cylinder set may then be defined by

$\backslash mu(C\_ta\_0,\backslash ldots,a\_s)\; =\; \backslash pi\_\{a\_0\}\; p\_\{a\_0,a\_1\}\; \backslash cdots\; p\_\{a\_\{s-1\},\; a\_s\}$

The Kolmogorov–Sinai entropy with relation to the Markov measure is

$s\_\backslash mu\; =\; -\backslash sum\_\{i=1\}^n\; \backslash pi\_i\; \backslash sum\_\{j=1\}^n\; p\_\{ij\}\; \backslash log\; p\_\{ij\}$

---

Zeta function The Artin–Mazur zeta function is defined as the formal power series

$\backslash zeta(z)=\backslash exp\backslash left(\backslash sum\_\{n=1\}^\backslash infty\; \backslash Bigl|\; \backslash textrm\{Fix\}\; (T^n)\; \backslash Bigr|\; \backslash frac\; \{z^n\}\{n\}\backslash right),$

where is the set of fixed points of the -fold shift. It has a product formula

$\backslash zeta(z)\; =\; \backslash prod\_\backslash gamma\; \backslash left(1-z^$ \right)^{-1} \

where runs over the closed orbits.Brin & Stuck (2002) p.60 For subshifts of finite type, the zeta function is a rational function of :Brin & Stuck (2002) p.61

$\backslash zeta(z)\; =\; (\backslash det(I-zA))^\{-1\}\; \backslash \; .$

---

See also

• Transfer operator
• De Bruijn graph
• Quantum finite automata
• Axiom A

---

Notes

• (2025). 9780521808415, Cambridge University Press. ISBN 9780521808415
• David Damanik, Strictly Ergodic Subshifts and Associated Operators, (2005)
• N. Pytheas Fogg (2025). 9783540441410, Springer-Verlag. ISBN 9783540441410
• Natasha Jonoska, Subshifts of Finite Type, Sofic Systems and Graphs, (2000).
• Michael S. Keane, Ergodic theory and subshifts of finite type, (1991), appearing as Chapter 2 in Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Tim Bedford, Michael Keane and Caroline Series, Eds. Oxford University Press, Oxford (1991). (Provides a short expository introduction, with exercises, and extensive references.)
• (1995). 9780521551243, Cambridge University Press. . ISBN 9780521551243
• Teschl (2025). 9780821883280, American Mathematical Society. . ISBN 9780821883280
• Huimin Xie (1996). 9789810223984, World Scientific. ISBN 9789810223984

---

Further reading

• (2025). 9780821831571, American Mathematical Society. ISBN 9780821831571

Post Comment